package pri.zjy.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangjy
 * @description 二叉树展开为链表
 * @date 2025/3/4 21:57
 */
public class Flatten_114 {

    public static void main(String[] args) {
        // TODO 比较先序遍历—>构造单链表的个人解法和官解区别？？前序遍历和展开同步进行？？寻找前驱节点？？
    }

    // 官解：先序遍历——>再构造单链表
    public void flatten1(TreeNode root) {
        // 分析：要展开为单链表，且链表顺序与树先序遍历顺序相同——>先序遍历，再构造单链表

        // 1.先序遍历，存储节点值
        List<TreeNode> nodes = new ArrayList<>();
        preorder1(root, nodes);

        // 2.构造单链表
        for (int i = 1; i < nodes.size(); i++) {
            TreeNode pre = nodes.get(i - 1);
            TreeNode cur = nodes.get(i);
            cur.left = null;
            cur.right = pre;
        }
    }

    public void preorder1(TreeNode node, List<TreeNode> nodes) {
        // 1.返回值、入参：(节点值集合)、（node、list）
        // 2.终止条件：node==null
        if (node == null) return;

        // 3.单层逻辑：根—>左—>右顺序记录节点node
        nodes.add(node);
        preorder1(node.left, nodes);
        preorder1(node.right, nodes);
    }

    // 个人解法-待完善
    public void flatten(TreeNode root) {
        // 分析：要展开为单链表，且链表顺序与树先序遍历顺序相同——>先序遍历，再构造单链表

        // 1.先序遍历，存储节点值
        List<Integer> vals = new ArrayList<>();
        preorder(root, vals);

        // 2.构造单链表
        List<TreeNode> nodes = new ArrayList<>(vals.size());
        for (int i = 0; i < vals.size(); i++) {
            TreeNode node = new TreeNode();
            node.val = vals.get(i);
            node.left = null;

            // TODO 这种方式，如何构造node的右节点？

//            node.right = ;
        }
    }

    public void preorder(TreeNode node, List<Integer> vals) {
        // 1.返回值、入参：(节点值集合)、（node、list）
        // 2.终止条件：node==null
        if (node == null) return;

        // 3.单层逻辑：根—>左—>右顺序记录节点值val
        vals.add(node.val);
        preorder(node.left, vals);
        preorder(node.right, vals);
    }

    class TreeNode {

        Integer val;

        TreeNode left;

        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(Integer val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

    }

}
